The invention relates generally to computerized techniques for processing data obtained from radar to track multiple discrete objects.
There are many situations where the courses of multiple objects in a region must be tracked. Typically, radar is used to scan the region and generate discrete images or "snapshots" based on sets of returns or observations. In some types of tracking systems, all the returns from any one object are represented in an image as a single point unrelated to the shape or size of the objects. "Tracking" is the process of identifying a sequence of points from a respective sequence of the images that represents the motion of an object. The tracking problem is difficult when there are multiple closely spaced objects because the objects can change their speed and direction rapidly and move into and out of the line of sight for other objects. The problem is exacerbated because each set of returns may result from noise as well as echoes from the actual objects. The returns resulting from the noise are also called false positives. Likewise, the radar will not detect all echoes from the actual objects and this phenomena is called a false negative or "missed detect" error. For tracking airborne objects, a large distance between the radar and the objects diminishes the signal to noise ratio so the number of false positives and false negatives can be high. For robotic applications, the power of the radar is low and as a result, the signal to noise ratio can also be low and the number of false positives and false negatives high.
In view of the proximity of the objects to one another, varied motion of the objects and false positives and false negatives, multiple sequential images should be analyzed collectively to obtain enough information to properly assign the points to the proper tracks. Naturally, the larger the number of images that are analyzed, the greater the amount of information that must be processed.
While identifying the track of an object, a kinematic model describing the object's location, velocity and acceleration may be generated. Such a model provides the means by which the object's future motion can be predicted. Based upon such a prediction, appropriate action may be initiated. For example, in a military application there is a need to track multiple enemy aircraft or missiles in a region to predict their objective, plan responses and intercept them. Alternatively, in a commercial air traffic control application there is a need to track multiple commercial aircraft around an airport to predict their future courses and avoid collision. Further, in these and other applications, such as robotic applications, may use radar, sonar, infrared or other object detecting radiation bandwidths for tracking objects. In particular, in robotic applications reflected radiation can be used to track a single object which moves relative to the robot (or vice versa) so the robot can work on the object.
Consider the very simple example of two objects being tracked and no false positives or false negatives. The radar, after scanning at time t.sub.1, reports objects at two locations in a first observation set. That is, it returns a set of two observations {o.sub.11, o.sub.12 }. At time t.sub.2 it returns a similar set of two observations {o.sub.21, o.sub.22) from a second observation set. Suppose from prior processing that track data for two tracks T.sub.1 and T.sub.2 includes the locations at t.sub.0 of two objects. Track T.sub.1 may be extended through the points in the two sets of observations in any of four ways, as may track T.sub.2. The possible extensions of T.sub.1 can be described as: {T.sub.1, o.sub.11, o.sub.21 }, {T.sub.1, o.sub.11, o.sub.22 }, {T.sub.1, o.sub.12, o.sub.21 } and {T.sub.1, o.sub.12, o.sub.22 }. Tracks can likewise be extended from T.sub.2 in four possible ways including, {T.sub.2, o.sub.12, o.sub.21 }. FIG. 1 illustrates these five (out of eight) possible tracks (to simplify the problem for purposes of explanation). The five track extensions are labeled h.sub.11, h.sub.12, h.sub.13, h.sub.14, and h.sub.21 wherein h.sub.11 is derived from {T.sub.1, o.sub.11, o.sub.21 }, h.sub.12 is derived from {T.sub.1, o.sub.11, o.sub.22 }, h.sub.13 is derived from {T.sub.1, o.sub.12, o.sub.21 }, h.sub.14 is derived from {T.sub.1, o.sub.12, o.sub.22 }, and h.sub.21 is derived from {T.sub.2, o.sub.11, o.sub.21 }. The problem of determining which such track extensions are the most likely or optimal is hereinafter known as the assignment problem.
It is known from prior art to determine a figure of merit or cost for assigning each of the points in the images to a track. The figure of merit or cost is based on the likelihood that the point is actually part of the track. For example, the figure of merit or cost may be based on the distance from the point to an extrapolation of the track. FIG. 1 illustrates costs .delta..sub.21 and .delta..sub.22 for hypothetical extension h.sub.21 and modeled target characteristics. The function to calculate the cost will normally incorporate detailed characteristics of the sensor, such as probability of measurement error, and track characteristics, such as likelihood of track maneuver.
FIG. 2 illustrates a two by two by two matrix, c, that contains the costs for each point in relation to each possible track. The cost matrix is indexed along one axis by the track number, along another axis by the image number and along the third axis by a point number. Thus, each position in the cost matrix lists the cost for a unique combination of points and a track, one point from each image. FIG. 2 also illustrates a {0, 1} assignment matrix, z, which is defined with the same dimensions as the cost matrix. Setting a position in the assignment matrix to "one" means that the equivalent position in the cost matrix is selected into the solution. The illustrated solution matrix selects the {h.sub.14, h.sub.21 } solution previously described. Note that for the above example of two tracks and two snapshots, the resulting cost and assignment matrices are three dimensional. As used in this patent application, the term "dimension" means the number of axes in the cost or assignment matrix while size refers to the number of elements along a typical axis. The costs and assignments have been grouped in matrices to facilitate computation.
A solution to the assignment problem satisfies two constraints--first, the sum of the associated costs for assigning points to a track extension is minimized and, second, if no false positives or false negatives exist, then each point is assigned to one and only one track.
When false positives exist, however, additional hypothetical track extensions incorporating the false positives will be generated. Further note that the random locations of false positives will, in general, not fit well with true data and such additional hypothetical track extensions will result in higher costs. Also note that when false negative errors exist, then the size of the cost matrix must grow to include hypothetical track extensions formulated with "gaps" (i.e., data omissions where there should be legitimate observation data) for the false negatives. Thus, the second criteria must be weakened to reflect false positives not being as signed and also to permit the gap filler to be multiply assigned. With hypothetical cost calculated in this manner then the foregoing criteria for minimization will tend to materialize the false negatives and avoid the false positives.
For a 3-dimensional problem, as is illustrated in FIG. 1, but with N.sub.1 (initial) tracks, N.sub.2 observations in scan 1, N.sub.3 observations in scan 2, false positives and negatives assumed, the assignment problem can be formulated as: ##EQU1## where "c" is the cost and "z" is a point or observation assignment, as in FIG. 2.
The minimization equation or equivalently objective function [1.0](a) specifies the sum of the element by element product of the c and z matrices. The summation includes hypothesis representations z.sub.i.sbsb.1.sub.i.sbsb.2.sub.i.sbsb.3 with observation number zero being the gap filler observation. Equation [1.0](b) requires that each of the tracks T.sub.1, . . . , T.sub.N.sbsb.1 be extended by one and only one hypothesis. Equation [1.0](c) relates to each point or observation in the first observation set and requires that each such observation, except the gap filler, can only associate with one track but because of the "less than" condition it might not associate with any track. Equation [1.0](d) is like [1.0](c) except that it is applicable to the second observation set. Equation [1.0](e) requires that elements of the solution matrix z be limited to the zero and one values.
The only known method to solve Problem Formulation [1.0] exactly is a method called "Branch and Bound." This method provides a systematic ordering of the potential solutions so that solutions with a same partial solution are accessible via a branch of a tree describing all possible solutions whereby the cost of unexamined solutions on a branch are incrementally developed as the cost for other solutions on the branch are determined. When the developing cost grows to exceed the previously known minimal cost (i.e., the bound) then enumeration of the tree branch terminates. Evaluation continues with a new branch. If evaluation of the cost of a particular branch completes, then that branch has lower cost than the previous bound so the new cost replaces the old bound. When all possible branches are evaluated or eliminated then the branch that had resulted in the last used bound is the solution. If we assume that N.sub.1 =N.sub.2 =N.sub.3 =n and that branches typically evaluate to half there full length, then workload associated with "branch and bound" is proportional to ##EQU2## This workload is unsuited to real time evaluation.
The Branch and Bound algorithm has been used in past research on the Traveling Salesman Problem. Messrs. Held and Karp showed that if the set of constraints was relaxed by a method of Lagrangian Multipliers (described in more detail below) then tight lower bounds could be developed in advance of enumerating any branch of the potential solution. By initiating the branch and bound algorithm with such a tight lower bound, significant performance improvements result in that branches will typically evaluate to less than half their full length.
Messrs. Frieze and Yadagar in dealing with a problem related to scheduling combinations of resources, as in job, worker and work site, showed that Problem Formulation [1.0] applied. They further described a solution method based upon an extension of the Lagrangian Relaxation previously mentioned. The two critical extensions provided by Messrs. Frieze and Yadagar were: (1) an iterative procedure that permitted the lower bound on the solution to be improved (by "hill climbing" described below) and (2) the recognition that when the lower bound of the relaxed problem was maximized, then there existed a method to recover the solution of the non-relaxed problem in most cases using parameters determined at the maximum. The procedures attributed to Messrs. Frieze and Yadagar are only applicable to the 3-dimensional problem posed by Problem Formulation [1.0] and where the cost matrix is fully populated. However, tracking multiple airborne objects usually requires solution of a much higher dimensional problem.
FIGS. 1 and 2 illustrate an example where "look ahead" data from the second image improved the assignment accuracy for the first image. Without the look ahead, and based only upon a simple nearest neighbor approach, the assignments in the first set would have been reversed. Problem Formulation [1.0] and the prior art only permit looking ahead one image. In the prior art it was known that the accuracy of assignments will improve if the process looks further ahead, however no practical method to optimally incorporate look ahead data existed. Many real radar tracking problems involve hundreds of tracks, thousands of observations per observation set and matrices with dimensions in the range of 3 to 25 including many images of look ahead.
It was also known that the data assignment problem may be simplified (without reducing the dimension of the assignment problem) by eliminating from consideration for each track those points which, after considering estimated limits of speed and turning ability of the objects, could not physically be part of the track. One such technique, denoted hereinafter the "cone method," defines a cone as a continuation of each previously determined track with the apex of the cone at the end of the previously defined track. The length of the cone is based on the estimated maximum speed of the object and the size of the arc of the cone is based on the estimated maximum turning ability of the object. Thus, the cone defines a region outside of which no point could physically be part of the respective track. For any such points outside of the cones, an infinite number could be put in the cost matrix and a zero could be preassigned in the assignment matrix. It was known for the tracking problem that these elements will be very common in the cost and selection matrices (so these matrices are "sparse").
It was also known in the prior art that one or more tracks which are substantially separated geographically from the other tracks can be separated also in the assignment problem. This is done by examining the distances from each point to the various possible tracks. If the distances from one set of points are reasonably short only in relation to one track, then they are assigned to that track and not further considered with the remainder of the points. Similarly, if a larger group of points can only be assigned to a few tracks, then the group is considered a different assignment problem. Because the complexity of assignment problems increases dramatically with the number of possible tracks and the total number of points in each matrix, this partitioning of the group of points into a separate assignment problem and removal of these points from the matrices for the remaining points, substantially reduces the complexity of the overall assignment problem.
A previously known Multiple Hypothesis Testing (MHT) algorithm (see Blackman, Multiple-Target Tracking with Radar Applications, Chapter 10, Artech House Norwood Mass., 1986) related to formulation and scoring. The MHT procedure describes how to formulate the sparse set of all reasonable extension hypothesis (for FIG. 1 the set {h.sub.11 . . . h.sub.24 }) and how to calculate a cost of the hypothesis {T.sub.i, o.sub.1j, o.sub.2k } based upon the previously calculated cost for hypothesis {T.sub.i, o.sub.1j }. The experience with the MHT algorithm, known in the prior art, is the basis for the assertion that look ahead through k sets of observations results in improved assignment of observations from the first set to the track.
In theory, the MHT procedure uses the extendable costing procedure to defer assignment decision until the accumulated evidence supporting the assignment becomes overwhelming. When it makes the assignment decision it then eliminates all potential assignments invalidated by the decision in a process called "pruning the tree." In practice, the MHT hypothesis tree is limited to a fixed number of generations and the overwhelming evidence rule is replaced by a most likely and feasible rule. This rule considers each track independently of others and is therefore a local decision rule.
A general object of the present invention is to provide an efficient and accurate process for assigning each point object in a region from multiple images to a proper track and then taking an action based upon the assignments.
A more specific object of the present invention is to provide a technique of the foregoing type which determines the solution of a k-dimensional assignment problem where "k" is greater than or equal to three.